{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Ambiguous Coordinates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: ambiguousCoordinates"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #模糊坐标"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>我们有一些二维坐标，如&nbsp;<code>&quot;(1, 3)&quot;</code>&nbsp;或&nbsp;<code>&quot;(2, 0.5)&quot;</code>，然后我们移除所有逗号，小数点和空格，得到一个字符串<code>S</code>。返回所有可能的原始字符串到一个列表中。</p>\n",
    "\n",
    "<p>原始的坐标表示法不会存在多余的零，所以不会出现类似于&quot;00&quot;, &quot;0.0&quot;, &quot;0.00&quot;, &quot;1.0&quot;, &quot;001&quot;, &quot;00.01&quot;或一些其他更小的数来表示坐标。此外，一个小数点前至少存在一个数，所以也不会出现&ldquo;.1&rdquo;形式的数字。</p>\n",
    "\n",
    "<p>最后返回的列表可以是任意顺序的。而且注意返回的两个数字中间（逗号之后）都有一个空格。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<pre>\n",
    "<strong>示例 1:</strong>\n",
    "<strong>输入:</strong> &quot;(123)&quot;\n",
    "<strong>输出:</strong> [&quot;(1, 23)&quot;, &quot;(12, 3)&quot;, &quot;(1.2, 3)&quot;, &quot;(1, 2.3)&quot;]\n",
    "</pre>\n",
    "\n",
    "<pre>\n",
    "<strong>示例 2:</strong>\n",
    "<strong>输入:</strong> &quot;(00011)&quot;\n",
    "<strong>输出:</strong> &nbsp;[&quot;(0.001, 1)&quot;, &quot;(0, 0.011)&quot;]\n",
    "<strong>解释:</strong> \n",
    "0.0, 00, 0001 或 00.01 是不被允许的。\n",
    "</pre>\n",
    "\n",
    "<pre>\n",
    "<strong>示例 3:</strong>\n",
    "<strong>输入:</strong> &quot;(0123)&quot;\n",
    "<strong>输出:</strong> [&quot;(0, 123)&quot;, &quot;(0, 12.3)&quot;, &quot;(0, 1.23)&quot;, &quot;(0.1, 23)&quot;, &quot;(0.1, 2.3)&quot;, &quot;(0.12, 3)&quot;]\n",
    "</pre>\n",
    "\n",
    "<pre>\n",
    "<strong>示例 4:</strong>\n",
    "<strong>输入:</strong> &quot;(100)&quot;\n",
    "<strong>输出:</strong> [(10, 0)]\n",
    "<strong>解释:</strong> \n",
    "1.0 是不被允许的。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示: </strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>4 &lt;= S.length &lt;= 12</code>.</li>\n",
    "\t<li><code>S[0]</code> = &quot;(&quot;, <code>S[S.length - 1]</code> = &quot;)&quot;, 且字符串&nbsp;<code>S</code>&nbsp;中的其他元素都是数字。</li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [ambiguous-coordinates](https://leetcode.cn/problems/ambiguous-coordinates/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [ambiguous-coordinates](https://leetcode.cn/problems/ambiguous-coordinates/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"(123)\"', '\"(0123)\"', '\"(00011)\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def f(i,j):\n",
    "            #这里的j最后在范围里是取不到的，但是我们允许其发生，即i+k==j,r为空，小数点后无东西即小数点最后\n",
    "            res=[]\n",
    "            for k in range(1,j-i+1):\n",
    "                l,r=s[i:i+k],s[i+k:j]\n",
    "                ok=(l =='0' or not l.startswith('0')) and not r.endswith('0')\n",
    "                if ok:\n",
    "                    res.append(l+('.' if k<j-i else '')+r)\n",
    "            return res\n",
    "        n=len(s)\n",
    "        return [f'({x}, {y})' for i in range(2,n-1) for x in f(1,i) for y in f(i,n-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "def findSplit(s: str) -> List[str]:\n",
    "    lis = []\n",
    "    if len(s) == 1 or s[0] != '0':\n",
    "        lis.append(s)\n",
    "            \n",
    "    for i in range(1, len(s)):\n",
    "        s1, s2 = s[:i], s[i:]\n",
    "        if (i == 1 or s[0] != '0') and s2[-1] != '0':\n",
    "            lis.append(s1+'.'+s2)\n",
    "    return lis\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        n, res = len(s), []\n",
    "        s = s[1: n - 1]\n",
    "\n",
    "        for i in range(1, n - 2):\n",
    "            part1, part2 = findSplit(s[:i]), findSplit(s[i:])\n",
    "            for a in part1:\n",
    "                for b in part2:\n",
    "                    res.append('('+a+', '+b+')')\n",
    "        \n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        # 分治法\n",
    "        def findSplit(part):\n",
    "            cur = []\n",
    "            if len(part) == 1 or part[0] != \"0\":\n",
    "                cur.append(part)\n",
    "            # 多0判断\n",
    "            for i in range(1,len(part)):\n",
    "                s1 = part[:i]\n",
    "                s2 = part[i:]\n",
    "                if (len(s1) == 1 or part[0] != \"0\") and s2[len(s2) - 1] != \"0\":\n",
    "                    cur.append(s1 + \".\" + s2)\n",
    "            return cur\n",
    "\n",
    "        n = len(s)\n",
    "        string = s[1:n - 1]\n",
    "        ans = list()\n",
    "        for i in range(1,n - 2):\n",
    "            # 体现分治思想\n",
    "            part1 = findSplit(string[:i])\n",
    "            part2 = findSplit(string[i:])\n",
    "            for a in part1:\n",
    "                for b in part2:\n",
    "                    ans.append(\"(\" + a + \", \" + b + \")\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_pos(s: str) -> List[str]:\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0' or s[-1] == '0':\n",
    "                    continue\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "        \n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1: len(s) - 1]\n",
    "        for l in range(1, n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "class Solution:\n",
    "        def subset(self,s):\n",
    "            ans = []\n",
    "            for i in range(1,len(s)):\n",
    "                if s[0] == '0' and i > 1:\n",
    "                    continue\n",
    "                if s[-1] == '0':\n",
    "                    continue\n",
    "                ans.append(s[:i] + '.' + s[i:])\n",
    "            if s == '0' or not s.startswith('0'):\n",
    "                ans.append(s)\n",
    "            return ans\n",
    "        def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "            ans = []\n",
    "            s = s[1:-1]\n",
    "            for i in range(1,len(s)):\n",
    "                X = self.subset(s[:i])\n",
    "                Y = self.subset(s[i:])\n",
    "                for x in X:\n",
    "                    for y in Y:\n",
    "                        ans.append('(' + x + ', ' + y + ')')\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_pos(s: str) -> List[str]:\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0' or s[-1] == '0':\n",
    "                    continue\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "\n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1: len(s) - 1]\n",
    "        for l in range(1, n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        s =  s[1:-1]\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        for i in range(1, n):\n",
    "            x = s[:i]\n",
    "            y = s[i:]\n",
    "            x_list = []\n",
    "            y_list = []\n",
    "            if len(x) == 1 or x[0] != '0':\n",
    "                x_list.append(x)\n",
    "            if len(x) > 1 and x[-1] != '0':\n",
    "                x_list.append(x[0] + '.' + x[1:])\n",
    "                if x[0] != '0':\n",
    "                    for j in range(2, len(x)):\n",
    "                        x_list.append(x[:j] + '.' + x[j:])\n",
    "            if len(y) == 1 or y[0] != '0':\n",
    "                y_list.append(y)\n",
    "            if len(y) > 1 and y[-1] != '0':\n",
    "                y_list.append(y[0] + '.' + y[1:])\n",
    "                if y[0] != '0':\n",
    "                    for j in range(2, len(y)):\n",
    "                        y_list.append(y[:j] + '.' + y[j:])\n",
    "            for xx, yy in product(x_list, y_list):\n",
    "                ans.append('(' + xx + ', ' + yy + ')')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        # 方法1、枚举\n",
    "        def get_pos(s):\n",
    "            pos = []\n",
    "            if s[0] != \"0\" or s == \"0\":\n",
    "                pos.append(s)\n",
    "            for p in range(1,len(s)):\n",
    "                if p != 1 and s[0] == \"0\" or s[-1] == \"0\":\n",
    "                    continue\n",
    "                pos.append(s[:p] + \".\" + s[p:])\n",
    "            return pos\n",
    "\n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1:len(s) - 1]\n",
    "        for l in range(1,n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i,j in product(lt,rt):\n",
    "                res.append(\"(\" + i + \", \" + j + \")\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def f(i,j):\n",
    "            res=[]\n",
    "            for k in range(1,j-i+1):\n",
    "                l,r=s[i:i+k],s[i+k:j]\n",
    "                ok=(l =='0' or not l.startswith('0')) and not r.endswith('0')\n",
    "                if ok:\n",
    "                    res.append(l+('.' if k<j-i else '')+r)\n",
    "            return res\n",
    "        n=len(s)\n",
    "        return [f'({x}, {y})' for i in range(2,n-1) for x in f(1,i) for y in f(i,n-1)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        s=s[1:-1]\n",
    "        def get_could_nums(s:str):\n",
    "            ans=[]\n",
    "            if s[0]=='0':\n",
    "                if len(s)==1:\n",
    "                    ans.append(s)\n",
    "                else:\n",
    "                    if s[-1]!='0':\n",
    "                        ans.append('0.'+s[1:])\n",
    "            else:\n",
    "                ans.append(s)\n",
    "                if s[-1]!='0':\n",
    "                    for i in range(len(s)-1):\n",
    "                        ans.append(s[:i+1]+'.'+s[i+1:])\n",
    "            return ans\n",
    "        ans=[]\n",
    "        for i in range(len(s)-1):\n",
    "            l=s[:i+1]\n",
    "            r=s[i+1:]\n",
    "            for nl in get_could_nums(l):\n",
    "                for nr in get_could_nums(r):\n",
    "                    ans.append(f'({nl}, {nr})')\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def f(i, j):\n",
    "            res = []\n",
    "            for k in range(1, j - i + 1):\n",
    "                l, r = s[i : i + k], s[i + k : j]\n",
    "                ok = (l == '0' or not l.startswith('0')) and not r.endswith('0')\n",
    "                if ok:\n",
    "                    res.append(l + ('.' if k < j - i else '') + r)\n",
    "            return res\n",
    "\n",
    "        n = len(s)\n",
    "        return [\n",
    "            f'({x}, {y})' for i in range(2, n - 1) for x in f(1, i) for y in f(i, n - 1)\n",
    "        ]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "\n",
    "\n",
    "        def findSplit(s):\n",
    "            lis=[]\n",
    "            if len(s)==1 or s[0]!='0':\n",
    "                lis.append(s)\n",
    "            for i in range(1, len(s)):\n",
    "                s1, s2 = s[:i], s[i:]\n",
    "                if (i == 1 or s[0] != '0') and s2[-1] != '0':\n",
    "                    lis.append(s1 + '.' + s2)\n",
    "            return lis\n",
    "        \n",
    "        n = len(s)\n",
    "        ans = []\n",
    "\n",
    "        s = s[1:n-1]\n",
    "        for i in range(1, n-2):\n",
    "            p1 = findSplit(s[:i])\n",
    "            p2 = findSplit(s[i:])\n",
    "            for a in p1:\n",
    "                for b in p2:\n",
    "                    ans.append('(' + a + ', ' + b + ')')\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def helper(s, l, r):\n",
    "            ans = []\n",
    "\n",
    "            if l == r or s[l] != '0':\n",
    "                ans.append(s[l:r+1])\n",
    "\n",
    "            for i in range(l, r):\n",
    "                a, b = s[l:i+1], s[i+1:r+1]\n",
    "                if len(a) > 1 and a[0] == '0':\n",
    "                    continue\n",
    "\n",
    "                if b[-1] == '0':\n",
    "                    continue\n",
    "                \n",
    "                ans.append(f'{a}.{b}')\n",
    "            return ans\n",
    "        \n",
    "        s = s[1:len(s)-1]\n",
    "        n =len(s)\n",
    "        ans = []\n",
    "\n",
    "        for i in range(n-1):\n",
    "            a, b = helper(s, 0, i), helper(s, i+1, n-1)\n",
    "\n",
    "            for x in a:\n",
    "                for y in b:\n",
    "                    ans.append(f'({x}, {y})')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # \"123\" => [\"1.23\", \"12.3\", \"123\"]\n",
    "    def subset(self, s: str):\n",
    "        ans = []\n",
    "\n",
    "        #  带小数点的\n",
    "        for i in range(1, len(s)):\n",
    "            # 不允许 00.111， 0.0，01.1，1.0\n",
    "            if s[0] == '0' and i > 1:\n",
    "                continue\n",
    "            if s[-1] == '0':\n",
    "                continue\n",
    "            ans.append(s[:i] + \".\" + s[i:])\n",
    "        # 不带小数点的（不允许 001）\n",
    "        if s == '0' or not s.startswith('0'):\n",
    "            ans.append(s)\n",
    "        return ans\n",
    "\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        s = s[1:-1]\n",
    "        for i in range(1, len(s)):\n",
    "            x = self.subset(s[:i])\n",
    "            y = self.subset(s[i:])\n",
    "            for i in x:\n",
    "                for j in y:\n",
    "                    ans.append('(' + i + ', ' + j + ')')\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        tab = {}\n",
    "\n",
    "        def find(s):\n",
    "            nonlocal tab\n",
    "            if len(s) == 1:\n",
    "                tab[s] = [s]\n",
    "                return tab[s]\n",
    "            if s in tab:\n",
    "                return tab[s]\n",
    "            else:\n",
    "                ls = []\n",
    "                for i in range(1, len(s)):\n",
    "                    if len(s[0:i]) > 1 and s[0] == '0':\n",
    "                        continue\n",
    "                    if s[-1] == '0':\n",
    "                        continue\n",
    "                    ls.append(s[0:i] + \".\" + s[i:])\n",
    "                if s[0] != '0':\n",
    "                    ls.append(s)\n",
    "                tab[s] = ls\n",
    "                return tab[s]\n",
    "\n",
    "        for i in range(2, n - 1):\n",
    "            x = s[1:i]\n",
    "            y = s[i:-1]\n",
    "            rx = find(x)\n",
    "            ry = find(y)\n",
    "            for k in range(len(rx)):\n",
    "                for j in range(len(ry)):\n",
    "                    ans.append(\"(\" + rx[k] + \", \" + ry[j] + \")\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_pos(s: str) -> List[str]:\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0' or s[-1] == '0':\n",
    "                    continue\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "\n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1: len(s) - 1]\n",
    "        for l in range(1, n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_pos(s: str) -> List[str]:\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0' or s[-1] == '0':\n",
    "                    continue\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "\n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1: len(s) - 1]\n",
    "        for l in range(1, n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        # 就是哪里放逗号，哪里放点的问题\n",
    "        s = s[1: -1]\n",
    "        n = len(s)\n",
    "        def check(ss):\n",
    "            if \".\" not in ss:\n",
    "                if len(ss) > 1 and ss[0] == '0':\n",
    "                    return False\n",
    "                return True\n",
    "            else:\n",
    "                idx = ss.index(\".\")\n",
    "                if idx == 0:\n",
    "                    return False\n",
    "                if ss[-1] == '0': return False\n",
    "                ss = ss[:idx]\n",
    "                if len(ss) > 1 and ss[0] == '0':\n",
    "                    return False\n",
    "                return True\n",
    "\n",
    "        ans = []\n",
    "        for i in range(1, n):\n",
    "            for j in range(i):\n",
    "                s1 = s[:j + 1] + \".\" + s[j + 1: i]\n",
    "                if s1[-1] == \".\": s1 = s1[: -1]\n",
    "                for k in range(i, n):\n",
    "                    s2 = s[i: k + 1] + \".\" + s[k + 1:]\n",
    "                    if s2[-1] == \".\": s2 = s2[: -1]\n",
    "                    if check(s1) and check(s2):\n",
    "                        ans.append(\"(\" + s1 + \", \" + s2 + \")\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        s = s[1:-1]\n",
    "        res = []\n",
    "        def f(s):\n",
    "            local = []\n",
    "            for i in range(1, len(s)):\n",
    "                cur = s[:i] + '.' + s[i:]\n",
    "                if check(cur):\n",
    "                    local.append(cur)\n",
    "            if check(s):\n",
    "                local.append(s)\n",
    "            return local\n",
    "        def check(s):\n",
    "            if len(s) == 1:\n",
    "                return True\n",
    "            elif s[0] == '0' and s[1] != '.':\n",
    "                return False\n",
    "            elif '.' in s and s[-1] == '0':\n",
    "                return False\n",
    "            return True\n",
    "        for i in range(1, len(s)):\n",
    "            left_res = f(s[:i])\n",
    "            right_res = f(s[i:])\n",
    "            if left_res and right_res:\n",
    "                for l in left_res:\n",
    "                    for r in right_res:\n",
    "                        res.append('({0}, {1})'.format(l, r))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def getPos(s: str) -> List[str]:\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0' or s[-1] == '0':\n",
    "                    continue\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "\n",
    "        s = s[1: len(s) - 1]\n",
    "        n = len(s)\n",
    "        res = []\n",
    "        for span in range(1, n):\n",
    "            lt = getPos(s[:span])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = getPos(s[span:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def judge(pos):\n",
    "    left,right = pos.split('.')\n",
    "    if len(left)>1 and left[0] == '0':\n",
    "        return False\n",
    "    if right[-1]=='0':\n",
    "        return False\n",
    "    return True\n",
    "\n",
    "def zuhe(x,y,pos_dict,res):\n",
    "    for i in range(len(x)):\n",
    "        if i != len(x)-1:\n",
    "            xx = x[:i+1]+'.'+x[i+1:]\n",
    "            do_x = judge(xx)\n",
    "        else:\n",
    "            xx = x\n",
    "            if len(xx)>1 and xx[0]=='0':\n",
    "                do_x = False\n",
    "            else:\n",
    "                do_x = True\n",
    "        for j in range(len(y)):\n",
    "            if j != len(y)-1:\n",
    "                yy = y[:j+1]+'.'+y[j+1:]\n",
    "                do_y = judge(yy)\n",
    "            else:\n",
    "                yy = y\n",
    "                if len(yy)>1 and yy[0]=='0':\n",
    "                    do_y = False\n",
    "                else:\n",
    "                    do_y = True\n",
    "            if do_x and do_y and (xx,yy) not in pos_dict.keys():\n",
    "                pos_dict[(xx,yy)] = True\n",
    "                res.append(\"(\"+xx+\", \"+yy+\")\")\n",
    "\n",
    "                \n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        s = s[1:-1]\n",
    "        res = []\n",
    "        pos_dict = {}\n",
    "        for i in range(1,len(s)):\n",
    "            x = s[:i]\n",
    "            y = s[i:]\n",
    "            zuhe(x,y,pos_dict,res)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        #枚举即可\n",
    "        def get_pos(s):\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0' or s[-1] == '0':\n",
    "                    continue\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1:-1]\n",
    "        for l in range(1, n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def str_to_int(s):\n",
    "            #将一个字符串转换成整数\n",
    "            if int(s[0])==0 and len(s)!=1:\n",
    "                return -1\n",
    "            return int(s)\n",
    "        def right_to_int(s):\n",
    "            #将一个浮点数小数部分是否满足要求\n",
    "            if len(s)!=0 and s[-1]!='0':\n",
    "                return s\n",
    "            return -1          \n",
    "        def str_to_float(s):\n",
    "            #将一个字符串转化成一个小数\n",
    "            n = len(s)\n",
    "            if s==1:\n",
    "                return -1\n",
    "            res = []#保存所有可能的结果\n",
    "            for i in range(n-1):\n",
    "                left = str_to_int(s[:i+1])\n",
    "                right = right_to_int(s[i+1:])\n",
    "                if left==-1 or (right==-1):\n",
    "                    continue\n",
    "                else:\n",
    "                    res.append(str(left)+'.'+right)\n",
    "            return res\n",
    "        \n",
    "        n = len(s)\n",
    "        s = s[1:n-1]\n",
    "        n=n-2\n",
    "        res = []\n",
    "        for i in range(n-1):\n",
    "            left = s[:i+1]            \n",
    "            right = s[i+1:]\n",
    "            left_int = str_to_int(left)\n",
    "            left_float = str_to_float(left)\n",
    "            right_int = str_to_int(right)\n",
    "            right_float = str_to_float(right)\n",
    "            if left_int !=-1:\n",
    "                if right_int!=-1:\n",
    "                    res.append('('+str(left_int)+', '+str(right_int)+')')\n",
    "                for item in right_float:\n",
    "                    res.append('('+str(left_int)+', '+item+')')\n",
    "            for item in left_float:\n",
    "                if right_int!=-1:\n",
    "                    res.append('('+item+', '+str(right_int)+')')\n",
    "                for item1 in right_float:\n",
    "                    res.append('('+item+', '+item1+')')\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution: \n",
    "    def checkNum(self, s:str) -> bool:\n",
    "        if len(s) == 0:\n",
    "            return False\n",
    "        cnt = s.count('.')        \n",
    "        if cnt == 0:\n",
    "            if s[0] == '0' and s != \"0\":\n",
    "                return False\n",
    "            return True\n",
    "        elif cnt == 1:\n",
    "            idx = s.index('.')\n",
    "            if idx == 0 or idx == len(s)-1:\n",
    "                return False\n",
    "            if s[0] == '0' and idx != 1:\n",
    "                return False           \n",
    "            if s[len(s)-1] == '0':\n",
    "                return False\n",
    "        else:\n",
    "            return False\n",
    "        return True\n",
    "\n",
    "    def check(self, s: str) -> bool:\n",
    "        s = s[1:len(s)-1]\n",
    "        if s.count(',') != 1:\n",
    "            return False\n",
    "        sp = s.split(\", \")\n",
    "        for ss in sp:\n",
    "            if not(self.checkNum(ss)):\n",
    "                return False\n",
    "        return True\n",
    "\n",
    "    def dfs(self, i: int, s: str, ret: List[str]):\n",
    "        if i >= len(s)-1:\n",
    "            if self.check(s):\n",
    "                ret.append(s)\n",
    "            return\n",
    "        self.dfs(i+1, s, ret)\n",
    "        self.dfs(i+2, s[:i] + '.' + s[i:], ret)\n",
    "        self.dfs(i+3, s[:i] + \", \" + s[i:], ret)        \n",
    "\n",
    "    def ambiguousCoordinates(self, ss: str) -> List[str]:\n",
    "        ret = []        \n",
    "        self.dfs(1, ss, ret)        \n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s) :\n",
    "        result = []\n",
    "        for douIdx in range(2, len(s) - 1):\n",
    "            preList = self.getValidStrList(s, 1, douIdx - 1)\n",
    "            postList = self.getValidStrList(s, douIdx, len(s)-2)\n",
    "            self.combine(preList, postList, result)\n",
    "        return result\n",
    "\n",
    "    def combine(self,preList:List[str] , postList:List[str] , result:List[str]):\n",
    "        for pre in preList:\n",
    "            for post in postList:\n",
    "                result.append('(' + pre + ', ' + post + ')')\n",
    "\n",
    "    def getValidStrList(self, s, start, end):\n",
    "        result = []\n",
    "        idx = start\n",
    "        while idx <= end:\n",
    "            pre = s[start:idx]\n",
    "            post = s[idx:end + 1]\n",
    "            tmp = post if pre == '' else pre + '.' + post\n",
    "            idx += 1\n",
    "            if self.check(tmp):\n",
    "                result.append(tmp)\n",
    "        return result\n",
    "        \n",
    "    def check(self,s:str) -> bool:\n",
    "        idx = s.find('.')\n",
    "        if idx > -1:\n",
    "            if idx == 0 or idx == len(s) - 1:\n",
    "                return False\n",
    "            zheng = s[:idx]\n",
    "            xiao = s[idx+1:]\n",
    "            return self.checkZheng(zheng) and self.checkXiao(xiao)\n",
    "        else:\n",
    "            return self.checkZheng(s)\n",
    "\n",
    "    \n",
    "    def checkZheng(self,s:str) -> bool:\n",
    "        if s == '0':\n",
    "            return True\n",
    "        return not s.startswith('0')\n",
    "\n",
    "    def checkXiao(self,s:str) -> bool:\n",
    "        return not s.endswith('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\r\n",
    "        #0 要么是0 要么是xxx0，要么是0.0xxx 0不能出现在小数的最后一个，不能在开头出现连续的0\r\n",
    "        def search(s,start,end):\r\n",
    "            cur_res = []\r\n",
    "            if start+1==end or s[start]!='0': \r\n",
    "                #长度为1的时候0可以单独成\r\n",
    "                #否则0开头的数据无效\r\n",
    "                cur_res.append(s[start:end])\r\n",
    "            for i in range(start+1,end):\r\n",
    "                a = s[start:i]#长度至少为1\r\n",
    "                b = s[i:end]#长度至少为1\r\n",
    "                if a[0]=='0' and len(a)!=1:\r\n",
    "                    continue\r\n",
    "                if b[-1]=='0':\r\n",
    "                    continue\r\n",
    "                cur_res.append(a+'.'+b)\r\n",
    "            return cur_res\r\n",
    "        s = s[1:-1]\r\n",
    "        res = []\r\n",
    "        for i in range(1,len(s)):\r\n",
    "            l_res = search(s,0,i)\r\n",
    "            r_res = search(s,i,len(s))\r\n",
    "            for l in l_res:\r\n",
    "                for r in r_res:\r\n",
    "                    res.append(\"({}, {})\".format(l,r))\r\n",
    "        return res\r\n",
    "\r\n",
    "            \r\n",
    "\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_candidate(t: str) -> List[str]:\n",
    "            res = []\n",
    "            n = len(t)\n",
    "            #----整数\n",
    "            if t == '0' or t[0] != '0':\n",
    "                res.append(t)\n",
    "            #----小数\n",
    "            for i in range(1, n):\n",
    "                L = t[ : i]\n",
    "                R = t[i : ]\n",
    "                if i != 1 and L[0] == '0':\n",
    "                    continue\n",
    "                if R[-1] == '0':\n",
    "                    continue\n",
    "                cur = L + '.' + R\n",
    "                res.append(cur)\n",
    "            return res            \n",
    "\n",
    "\n",
    "        n = len(s) - 2\n",
    "        s = s[1:-1]\n",
    "        res = []\n",
    "        for i in range(1, n):\n",
    "            L = s[:i]\n",
    "            R = s[i:]\n",
    "            ll = get_candidate(L)\n",
    "            rr = get_candidate(R)\n",
    "            if ll and rr:\n",
    "                for x in ll:\n",
    "                    for y in rr:\n",
    "                        cur = '(' + x + ', ' + y + ')'\n",
    "                        res.append(cur)\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        res=[]\n",
    "\n",
    "        s=s[1:-1]\n",
    "        \n",
    "        zhong=s[1:-1]\n",
    "        for i in range(len(zhong),-1,-1):\n",
    "            tou=s[0]\n",
    "            wei=s[-1]\n",
    "            tou+=zhong[:i]\n",
    "            wei=zhong[i:]+wei\n",
    "            # print(tou,wei)\n",
    "            # if tou[0]!=0:\n",
    "            #     res.append((tou,wei))\n",
    "\n",
    "            for j in range(len(tou)):\n",
    "                if j==len(tou)-1:\n",
    "                    tou_temp=tou\n",
    "                    if len(tou_temp)>1:\n",
    "                            if tou_temp[0]==\"0\":\n",
    "                                    continue\n",
    "                                  \n",
    "                else:\n",
    "                    tou_temp=tou[:j+1]+\".\"+tou[j+1:]\n",
    "                    if len(tou_temp)>1:\n",
    "                        if tou_temp[0]==\"0\" and tou_temp[1] !=\".\":\n",
    "                            continue\n",
    "                        \n",
    "                        if tou_temp[-1]==\"0\":\n",
    "                            continue\n",
    "                \n",
    "                    \n",
    "                    \n",
    "                \n",
    "\n",
    "                for k in range(len(wei)):\n",
    "                    if k==len(wei)-1:\n",
    "                        wei_temp=wei\n",
    "                        if len(wei_temp)>1:\n",
    "                            if wei_temp[0]==\"0\":\n",
    "                                    continue\n",
    "                            \n",
    "                    else:\n",
    "                        wei_temp=wei[:k+1]+\".\"+wei[k+1:]\n",
    "                        if len(wei_temp)>1:\n",
    "                            if wei_temp[0]==\"0\" and wei_temp[1] !=\".\":\n",
    "                                continue\n",
    "                            \n",
    "                            if wei_temp[-1]==\"0\":\n",
    "                                continue\n",
    "                    \n",
    "                    print(tou_temp,wei_temp)\n",
    "                    temp=\"(\"+tou_temp+\", \"+wei_temp+\")\"\n",
    "                    res.append(temp)\n",
    "        return res\n",
    "                \n",
    " \n",
    "\n",
    "                    \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "\n",
    "        # 可以扩展为n元坐标合法性的回溯\n",
    "\n",
    "        s = s[1:-1]\n",
    "        n = len(s)\n",
    "\n",
    "        def constructNumber(s):\n",
    "            i = len(s)\n",
    "            nums = []\n",
    "            if i == 1:\n",
    "                nums.append(s[0])\n",
    "            elif s[0] == \"0\":\n",
    "                if i > 1 and s[i-1] == \"0\": #and int(s[:i]) == 0:\n",
    "                    return []\n",
    "                else:\n",
    "                    nums.append(\"0.\" + s[1:i])\n",
    "            elif s[i-1] == \"0\":\n",
    "                nums.append(s[:i])\n",
    "            else:\n",
    "                for j in range(1,i):\n",
    "                    # [0,j-1] [j,i-1] interger/decimal   [0,0] [1,i-1] ... [0,i-1] [i,i-1] 只有整数\n",
    "                    nums.append(s[:j] + \".\" +s[j:i])\n",
    "                nums.append(s[:i])\n",
    "            return nums\n",
    "\n",
    "        res = []\n",
    "        for i in range(1,n):\n",
    "            # [0,i-1] [i,n-1]\n",
    "            # s[:i]   s[i:]   for i = 1...n-1\n",
    "            \n",
    "            # 第一个数 如果start with 0/ end with 0 都需要特殊处理, 写完发现生成两个数的逻辑是一样的，提出去做util函数\n",
    "            nums1 = constructNumber(s[:i])\n",
    "\n",
    "            # 第二个数 s[i:]\n",
    "            nums2 = constructNumber(s[i:])\n",
    "\n",
    "            for n1 in nums1:\n",
    "                for n2 in nums2:\n",
    "                    res.append(f\"({n1}, {n2})\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        num = s[1:(len(s)-1)]\n",
    "        n = len(num)\n",
    "        if n==2:\n",
    "            return [\"(\"+num[0]+\", \"+num[1]+\")\"]\n",
    "        temp = []\n",
    "        for i in range(1,n):\n",
    "            temp.append((num[:i],num[i:]))\n",
    "        def extract_num(ss):\n",
    "            nn = []\n",
    "            if ss!='0':\n",
    "                if ss[-1] == '0' and ss[0] == '0':\n",
    "                    return nn\n",
    "                elif len(ss)>1 and ss[-1]!='0' and ss[0]!='0':\n",
    "                    nn.append(ss)\n",
    "                    nn.extend([ss[:i]+'.'+ss[i:] for i in range(1,len(ss))])\n",
    "                elif ss[0]=='0':\n",
    "                    nn.append('0.'+ss[1:])\n",
    "                elif ss[0]!='0':\n",
    "                    nn.append(ss)\n",
    "            else:\n",
    "                nn.append(ss)\n",
    "            return nn\n",
    "        res = []\n",
    "        for x1,x2 in temp:\n",
    "            tmp1 = extract_num(x1)\n",
    "            tmp2 = extract_num(x2)\n",
    "            while tmp1 and tmp2:\n",
    "                xx = tmp1.pop()\n",
    "                res.extend([\"(\"+xx+\", \"+x+\")\" for x in tmp2])\n",
    "        return res\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s) :\n",
    "        result = []\n",
    "        for douIdx in range(2, len(s) - 1):\n",
    "            preList = self.abc(s, 1, douIdx - 1)\n",
    "            postList = self.abc(s, douIdx, len(s)-2)\n",
    "            self.cbd(preList, postList, result)\n",
    "        return result\n",
    "\n",
    "    def cbd(self,preList:List[str] , postList:List[str] , result:List[str]):\n",
    "        for pre in preList:\n",
    "            for post in postList:\n",
    "                result.append('(' + pre + ', ' + post + ')')\n",
    "\n",
    "    def abc(self, s, start, end):\n",
    "        result = []\n",
    "        idx = start\n",
    "        while idx <= end:\n",
    "            pre = s[start:idx]\n",
    "            post = s[idx:end + 1]\n",
    "            tmp = post if pre == '' else pre + '.' + post\n",
    "            idx += 1\n",
    "            if self.check(tmp):\n",
    "                result.append(tmp)\n",
    "        return result\n",
    "        \n",
    "    def check(self,s:str) -> bool:\n",
    "        idx = s.find('.')\n",
    "        if idx > -1:\n",
    "            if idx == 0 or idx == len(s) - 1:\n",
    "                return False\n",
    "            zheng = s[:idx]\n",
    "            xiao = s[idx+1:]\n",
    "            return self.checkZheng(zheng) and self.checkXiao(xiao)\n",
    "        else:\n",
    "            return self.checkZheng(s)\n",
    "\n",
    "    \n",
    "    def checkZheng(self,s:str) -> bool:\n",
    "        if s == '0':\n",
    "            return True\n",
    "        return not s.startswith('0')\n",
    "\n",
    "    def checkXiao(self,s:str) -> bool:\n",
    "        return not s.endswith('0')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_pos(s: str) -> List[str]:\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "\n",
    "            for p in range(1, len(s)):\n",
    "                if (p != 1 and s[0] == '0') or s[-1] == '0':\n",
    "                    continue\n",
    "\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "\n",
    "            return pos\n",
    "\n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1: len(s) - 1]\n",
    "        for l in range(1, n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def func(s):\n",
    "            res = []\n",
    "            if s[0] != '0' or len(s) == 1:\n",
    "                res.append(s)\n",
    "            for length in range(1, len(s)):\n",
    "                l, r = s[:length], s[length:]\n",
    "                if int(r) == 0 or r[-1] == '0':\n",
    "                    continue\n",
    "                if l[0] != '0' or len(l) == 1:\n",
    "                    res.append(l + '.' + r)\n",
    "            return res\n",
    "        \n",
    "        s = s[1:-1]\n",
    "        res = []\n",
    "        for left_length in range(1, len(s)):\n",
    "            for v1 in func(s[:left_length]):\n",
    "                for v2 in func(s[left_length:]):\n",
    "                    cur = '(' + v1 + ', ' + v2 + ')'\n",
    "                    res.append(cur)\n",
    "        return res\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_part(c):\n",
    "            res=[]\n",
    "            m=len(c)\n",
    "            #枚举逗号\n",
    "            for j in range(1,m):\n",
    "                if (j>1 and c[0]==\"0\") or c[-1]==\"0\":\n",
    "                    continue\n",
    "                res.append(c[:j]+\".\"+c[j:])\n",
    "            if m>1 and c[0]==\"0\":\n",
    "                return res\n",
    "            res.append(c)\n",
    "            return res\n",
    "        #枚举逗号和分号即可\n",
    "        s=s[1:-1]\n",
    "        n=len(s)\n",
    "        ans=[]\n",
    "        #枚举逗号\n",
    "        for i in range(1,n):\n",
    "            left=s[:i]\n",
    "            a=get_part(left)\n",
    "            if len(a)==0:\n",
    "                continue\n",
    "            right=s[i:]\n",
    "            b=get_part(right)\n",
    "            if len(b)==0:\n",
    "                continue\n",
    "            for i in range(len(a)):\n",
    "                for j in range(len(b)):\n",
    "                    ans.append(\"(\"+a[i]+\", \"+b[j]+\")\")\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        # s = s[1:-1]  # Removing the brackets\n",
    "\n",
    "        # def isValid(num: str) -> bool:\n",
    "        #     # Check if the number is a valid integer or decimal\n",
    "        #     if len(num) > 1 and num[0] == '0' and '.' not in num:\n",
    "        #         return False\n",
    "        #     if num[-1] == '0' and '.' in num:\n",
    "        #         return False\n",
    "        #     return True\n",
    "\n",
    "        # def generateNumbers(part: str) -> List[str]:\n",
    "        #     # Generate all possible valid numbers by inserting a decimal point\n",
    "        #     n = len(part)\n",
    "        #     if n == 1:\n",
    "        #         return [part]\n",
    "        #     if part[0] == '0':\n",
    "        #         if part[-1] == '0':\n",
    "        #             return []\n",
    "        #         else:\n",
    "        #             return [f\"{part[:1]}.{part[1:]}\"]\n",
    "        #     if part[-1] == '0':\n",
    "        #         return [part]\n",
    "        #     ans = [part]\n",
    "        #     for i in range(1, n):\n",
    "        #         ans.append(f\"{part[:i]}.{part[i:]}\")\n",
    "        #     return [x for x in ans if isValid(x)]\n",
    "        \n",
    "        # ans = []\n",
    "        # for i in range(1, len(s)):\n",
    "        #     left, right = s[:i], s[i:]\n",
    "        #     for l in generateNumbers(left):\n",
    "        #         for r in generateNumbers(right):\n",
    "        #             ans.append(f\"({l}, {r})\")\n",
    "        # return ans\n",
    "        s=s[1:-1]\n",
    "        n=len(s)\n",
    "        ans =[]\n",
    "        def dfs(s,path):\n",
    "            if  not s or len(path)==n:\n",
    "                ans.append(path)\n",
    "            for i in range(len(s)):\n",
    "                dfs(s[i+1:], path+[s[:i+1]])\n",
    "        dfs(s,[])\n",
    "        cache = defaultdict(int)\n",
    "        ans =[\n",
    "            ians\n",
    "            for ians in ans if len(ians)==2\n",
    "\n",
    "        ]\n",
    "        def isValid(num: str) -> bool:\n",
    "            # Check if the number is a valid integer or decimal\n",
    "            if len(num) > 1 and num[0] == '0' and '.' not in num:\n",
    "                return False\n",
    "            if num[-1] == '0' and '.' in num:\n",
    "                return False\n",
    "            return True\n",
    "\n",
    "        def generateNumbers(part: str) -> List[str]:\n",
    "            # Generate all possible valid numbers by inserting a decimal point\n",
    "            n = len(part)\n",
    "            if n == 1:\n",
    "                return [part]\n",
    "            if part[0] == '0':\n",
    "                if part[-1] == '0':\n",
    "                    return []\n",
    "                else:\n",
    "                    return [f\"{part[:1]}.{part[1:]}\"]\n",
    "            if part[-1] == '0':\n",
    "                return [part]\n",
    "            ans = [part]\n",
    "            for i in range(1, n):\n",
    "                ans.append(f\"{part[:i]}.{part[i:]}\")\n",
    "            return [x for x in ans if isValid(x)]\n",
    "\n",
    "        res=[]\n",
    "        \n",
    "        for (k,v) in ans:\n",
    "            for ks in generateNumbers(k):\n",
    "               for  vs in generateNumbers(v):\n",
    "                    res.append(f\"({ks}, {vs})\")\n",
    "\n",
    "         \n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        s = s[1: len(s) - 1]\n",
    "        n, ans = len(s), []\n",
    "        def get(st, ed):\n",
    "            ret = []\n",
    "            if st == ed:\n",
    "                ret.append(s[st])\n",
    "            elif s[st] == '0' and s[ed] == '0': return ret\n",
    "            elif s[st] == '0': ret.append('0.' + s[st + 1: ed + 1])\n",
    "            elif s[ed] == '0': ret.append(s[st: ed + 1])\n",
    "            else:\n",
    "                ret.append(s[st: ed + 1])\n",
    "                for i in range(st + 1, ed + 1): ret.append(s[st: i] + '.' + s[i: ed + 1])\n",
    "            return ret\n",
    "        for i in range(n - 1):\n",
    "            ret1 = get(0, i)\n",
    "            if not ret1: continue\n",
    "            ret2 = get(i + 1, n - 1)\n",
    "            for v1 in ret1:\n",
    "                for v2 in ret2: ans.append('(' + v1 + ', ' + v2 + ')')\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "\n",
    "\n",
    "        def findSplit(s):\n",
    "            lis=[]\n",
    "            \n",
    "            if len(s) == 1:\n",
    "                lis.append(s)\n",
    "            else:\n",
    "                if s[0] != '0':\n",
    "                    lis.append(s)\n",
    "            for i in range(1, len(s)):\n",
    "                s1, s2 = s[:i], s[i:]\n",
    "                if (i == 1 or s[0] != '0') and s2[-1] != '0':\n",
    "                    lis.append(s1 + '.' + s2)\n",
    "            return lis\n",
    "        \n",
    "        n = len(s)\n",
    "        ans = []\n",
    "\n",
    "        s = s[1:n-1]\n",
    "        for i in range(1, n-2):\n",
    "            p1 = findSplit(s[:i])\n",
    "            p2 = findSplit(s[i:])\n",
    "            for a in p1:\n",
    "                for b in p2:\n",
    "                    ans.append('(' + a + ', ' + b + ')')\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_pos(s: str) -> List[str]:\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0' or s[-1] == '0':\n",
    "                    continue\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "\n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1: len(s) - 1]\n",
    "        for l in range(1, n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\r\n",
    "        ans = []\r\n",
    "        for i in range(1, len(s) - 2):\r\n",
    "            ans.append(s[:i+1] + ', ' + s[i+1:])\r\n",
    "\r\n",
    "        # 前面加一个逗号\r\n",
    "        nex = []\r\n",
    "        for v in ans:\r\n",
    "            for i in range(1, len(v) - 1):\r\n",
    "                if v[i + 1] == ',':\r\n",
    "                    break\r\n",
    "                nex.append(v[:i+1] + '.' + v[i+1:])\r\n",
    "        ans += nex\r\n",
    "\r\n",
    "        # 后面加一个逗号\r\n",
    "        nex = []\r\n",
    "        for v in ans:\r\n",
    "            ind = v.index(' ')\r\n",
    "            for i in range(ind + 1, len(v) - 2):\r\n",
    "                nex.append(v[:i+1] + '.' + v[i+1:])\r\n",
    "        ans += nex\r\n",
    "        print(ans)\r\n",
    "\r\n",
    "        # 删除不合法的\r\n",
    "        res = []\r\n",
    "        for v in ans:\r\n",
    "            arr = []\r\n",
    "            tmp = ''\r\n",
    "            for i in range(1, len(v)):\r\n",
    "                if v[i] in '0123456789.':\r\n",
    "                    tmp += v[i]\r\n",
    "                elif v[i] in ',)':\r\n",
    "                    arr.append(tmp)\r\n",
    "                    tmp = ''\r\n",
    "            \r\n",
    "            flag = True\r\n",
    "            for i in range(len(arr)):\r\n",
    "                tmp = arr[i].split('.')\r\n",
    "                for j in range(min(2, len(tmp))):\r\n",
    "                    if j == 0:\r\n",
    "                        if str(int(tmp[j])) != tmp[j]:\r\n",
    "                            flag = False\r\n",
    "                            break\r\n",
    "                    else:\r\n",
    "                        if tmp[j][-1] == '0':\r\n",
    "                            flag = False\r\n",
    "                            break\r\n",
    "            if flag:\r\n",
    "                res.append(v)\r\n",
    "\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\r\n",
    "        ans = []\r\n",
    "        for i in range(1, len(s) - 2):\r\n",
    "            ans.append(s[:i+1] + ', ' + s[i+1:])\r\n",
    "\r\n",
    "        # 前面加一个逗号\r\n",
    "        nex = []\r\n",
    "        for v in ans:\r\n",
    "            for i in range(1, len(v) - 1):\r\n",
    "                if v[i + 1] == ',':\r\n",
    "                    break\r\n",
    "                nex.append(v[:i+1] + '.' + v[i+1:])\r\n",
    "        ans += nex\r\n",
    "\r\n",
    "        # 后面加一个逗号\r\n",
    "        nex = []\r\n",
    "        for v in ans:\r\n",
    "            ind = v.index(' ')\r\n",
    "            for i in range(ind + 1, len(v) - 2):\r\n",
    "                nex.append(v[:i+1] + '.' + v[i+1:])\r\n",
    "        ans += nex\r\n",
    "\r\n",
    "        # 删除不合法的\r\n",
    "        res = []\r\n",
    "        for v in ans:\r\n",
    "            arr = []\r\n",
    "            tmp = ''\r\n",
    "            for i in range(1, len(v)):\r\n",
    "                if v[i] in '0123456789.':\r\n",
    "                    tmp += v[i]\r\n",
    "                elif v[i] in ',)':\r\n",
    "                    arr.append(tmp)\r\n",
    "                    tmp = ''\r\n",
    "            \r\n",
    "            flag = True\r\n",
    "            for i in range(len(arr)):\r\n",
    "                tmp = arr[i].split('.')\r\n",
    "                for j in range(min(2, len(tmp))):\r\n",
    "                    if j == 0:\r\n",
    "                        if str(int(tmp[j])) != tmp[j]:\r\n",
    "                            flag = False\r\n",
    "                            break\r\n",
    "                    else:\r\n",
    "                        if tmp[j][-1] == '0':\r\n",
    "                            flag = False\r\n",
    "                            break\r\n",
    "            if flag:\r\n",
    "                res.append(v)\r\n",
    "\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_pos(s: str):\n",
    "            if len(s) == 1:\n",
    "                return [s]  #只有一个肯定是ok的\n",
    "            pos = []\n",
    "            if s[0] != '0': pos.append(s)  #保留整个\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0': #先导0\n",
    "                    continue\n",
    "                if s[-1] == '0':\n",
    "                    continue #后导0                    \n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "        length = len(s)\n",
    "        s = s[1:length-1]\n",
    "        length -= 2\n",
    "        res = []\n",
    "        for i in range(1,length):\n",
    "            left, right = s[:i], s[i:]  #得到左右\n",
    "            lt = get_pos(left)\n",
    "            #判断左右的合法性\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(right)\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\r\n",
    "        # 添加逗号\r\n",
    "        ans = []\r\n",
    "        for i in range(1, len(s) - 2):\r\n",
    "            ans.append(s[:i+1] + ', ' + s[i+1:])\r\n",
    "\r\n",
    "        # 前面加一个小数点\r\n",
    "        nex = []\r\n",
    "        for v in ans:\r\n",
    "            for i in range(1, len(v) - 1):\r\n",
    "                if v[i + 1] == ',':\r\n",
    "                    break\r\n",
    "                nex.append(v[:i+1] + '.' + v[i+1:])\r\n",
    "        ans += nex\r\n",
    "\r\n",
    "        # 后面加一个小数点\r\n",
    "        nex = []\r\n",
    "        for v in ans:\r\n",
    "            ind = v.index(' ')\r\n",
    "            for i in range(ind + 1, len(v) - 2):\r\n",
    "                nex.append(v[:i+1] + '.' + v[i+1:])\r\n",
    "        ans += nex\r\n",
    "\r\n",
    "        # 删除不合法的\r\n",
    "        res = []\r\n",
    "        for v in ans:\r\n",
    "            arr = []\r\n",
    "            tmp = ''\r\n",
    "            for i in range(1, len(v)):\r\n",
    "                if v[i] in '0123456789.':\r\n",
    "                    tmp += v[i]\r\n",
    "                elif v[i] in ',)':\r\n",
    "                    arr.append(tmp)\r\n",
    "                    tmp = ''\r\n",
    "            \r\n",
    "            flag = True\r\n",
    "            for i in range(len(arr)):\r\n",
    "                tmp = arr[i].split('.')\r\n",
    "                for j in range(min(2, len(tmp))):\r\n",
    "                    if j == 0:\r\n",
    "                        if str(int(tmp[j])) != tmp[j]:\r\n",
    "                            flag = False\r\n",
    "                            break\r\n",
    "                    else:\r\n",
    "                        if tmp[j][-1] == '0':\r\n",
    "                            flag = False\r\n",
    "                            break\r\n",
    "            if flag:\r\n",
    "                res.append(v)\r\n",
    "\r\n",
    "        return(res)\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\r\n",
    "\r\n",
    "        def parse(start,end):\r\n",
    "            l=end-start+1\r\n",
    "            if l==1:\r\n",
    "                return [s[start]]\r\n",
    "            prefix=s[start]=='0'\r\n",
    "            suffix=s[end]=='0'\r\n",
    "            if prefix and suffix:\r\n",
    "                return []\r\n",
    "            ret=[]\r\n",
    "            if not prefix:\r\n",
    "                ret.append(s[start:end+1])\r\n",
    "                if not suffix:\r\n",
    "                    for i in range(1,l):\r\n",
    "                        ret.append(s[start:start+i]+'.'+s[start+i:end+1])\r\n",
    "            elif not suffix:\r\n",
    "                ret.append('0.'+s[start+1:end+1])\r\n",
    "            return ret\r\n",
    "\r\n",
    "        s=s[1:-1]\r\n",
    "        L=len(s)\r\n",
    "        ret=[]\r\n",
    "        for i in range(1,L):\r\n",
    "            left_parts=parse(0,i-1)\r\n",
    "            if not left_parts:\r\n",
    "                continue\r\n",
    "            right_parts=parse(i,L-1)\r\n",
    "            if not right_parts:\r\n",
    "                continue\r\n",
    "            for left in left_parts:\r\n",
    "                for right in right_parts:\r\n",
    "                    ret.append(f'({left}, {right})')\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    ### 这是一个递归，他不用恢复现场\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_candidate(t: str) -> List[str]:\n",
    "            res = []\n",
    "            n = len(t)\n",
    "            #----整数\n",
    "            if t == '0' or t[0] != '0':\n",
    "                res.append(t)\n",
    "            #----小数\n",
    "            for i in range(1, n):\n",
    "                L = t[ : i]\n",
    "                R = t[i : ]\n",
    "                if i != 1 and L[0] == '0':\n",
    "                    continue\n",
    "                if R[-1] == '0':\n",
    "                    continue\n",
    "                cur = L + '.' + R\n",
    "                res.append(cur)\n",
    "            return res            \n",
    "\n",
    "\n",
    "        n = len(s) - 2\n",
    "        s = s[1:-1] ## 拿掉括号\n",
    "        res = []\n",
    "        for i in range(1, n):\n",
    "            L = s[:i]\n",
    "            R = s[i:]\n",
    "            ll = get_candidate(L)\n",
    "            rr = get_candidate(R)\n",
    "            if ll and rr:\n",
    "                for x in ll:\n",
    "                    for y in rr:\n",
    "                        cur = '(' + x + ', ' + y + ')'\n",
    "                        res.append(cur)\n",
    "        return res\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    # \"123\" => [\"1.23\", \"12.3\", \"123\"]\n",
    "    def subset(self, s: str):\n",
    "        ans = []\n",
    "\n",
    "        #  带小数点的\n",
    "        for i in range(1, len(s)):\n",
    "            # 不允许 00.111， 0.0，01.1，1.0\n",
    "            if s[0] == '0' and i > 1:\n",
    "                continue\n",
    "            if s[-1] == '0':\n",
    "                continue\n",
    "            ans.append(s[:i] + \".\" + s[i:])\n",
    "        # 不带小数点的（不允许 001）\n",
    "        if s == '0' or not s.startswith('0'):\n",
    "            ans.append(s)\n",
    "        return ans\n",
    "\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        ans = []\n",
    "        s = s[1:-1]\n",
    "        for i in range(1, len(s)):\n",
    "            x = self.subset(s[:i])\n",
    "            y = self.subset(s[i:])\n",
    "            for i in x:\n",
    "                for j in y:\n",
    "                    ans.append('(' + i + ', ' + j + ')')\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get(t):\n",
    "            res = []\n",
    "            n = len(t)\n",
    "            if len(t) == 1 or t[0] != '0':\n",
    "                res.append(t)\n",
    "            for i in range(n - 1):\n",
    "                a, b = t[:i+1], t[i+1:]\n",
    "                if len(a) > 1 and a[0] == '0':\n",
    "                    continue\n",
    "                if b[-1] == '0':\n",
    "                    continue\n",
    "                res.append(f'{a}.{b}')\n",
    "            return res\n",
    "\n",
    "        s = s[1:-1]\n",
    "        # print(f'{s}')\n",
    "        n = len(s)\n",
    "        ans = []\n",
    "        for i in range(n-1):\n",
    "            x = s[:i + 1]\n",
    "            y = s[i + 1:]\n",
    "            a1 = get(x)\n",
    "            a2 = get(y)\n",
    "            # print(f'{a1},{a2}')\n",
    "            for v1 in a1:\n",
    "                for v2 in a2:\n",
    "                    ans.append(f'({v1}, {v2})')\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_pos(s: str) -> List[str]:\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0' or s[-1] == '0':\n",
    "                    continue\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "\n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1: len(s) - 1]\n",
    "        for l in range(1, n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "\n",
    "        s = s[1:-1]\n",
    "        n = len(s)\n",
    "\n",
    "        def constructNumber(s):\n",
    "            \"\"\" \n",
    "                考虑s 在可以添加小数点的情况下能生成的所有合法数字 \n",
    "                可以扩展为k元坐标合法性的回溯, 划分每个数后再点小数点的逻辑是一样的\n",
    "            \"\"\"\n",
    "            i = len(s)\n",
    "\n",
    "            if s[0] == \"0\": # 如果以0开头, 输出整数只能为0本身，小数只能在第一个0后面添加 (0.0xxx合法  00.xx不合法 0.xxx000 不合法)\n",
    "                if i == 1:\n",
    "                    return [\"0\"]\n",
    "                elif i > 1 and s[i-1] == \"0\": # 如果是 0.xxx000 0.000 以0结尾的小数不合法，返回空数组\n",
    "                    return []\n",
    "                else:\n",
    "                    return [\"0.\" + s[1:i]] #不以0结尾，则能生成的唯一小数\n",
    "            elif s[i-1] == \"0\": # 如果不以0为开头, 却以0为结尾，则只能生成以0为结尾的整数 100合法 10.0、1.00 非法\n",
    "                return [s[:i]]\n",
    "\n",
    "            #else: 首位都不为0，小数点可以点在任意位置\n",
    "            nums = []\n",
    "            for j in range(1,i):\n",
    "                # [0,j-1] [j,i-1] interger/decimal   [0,0]-[1,i-1] ... [0,i-2]-[i-1,i-1] \n",
    "                nums.append(s[:j] + \".\" +s[j:i])\n",
    "            nums.append(s[:i]) #[0,i-1] 整数\n",
    "            return nums\n",
    "\n",
    "        res = []\n",
    "        for i in range(1,n):\n",
    "            \"\"\" \n",
    "            考虑 以i作为第二个数字的开头, 划分前后两个数字\n",
    "            [0,i-1]   [i,n-1]\n",
    "            \"\"\"\n",
    "            # s[:i]   s[i:]   for i = 1...n-1\n",
    "            \n",
    "            # 第一个数 如果start/end with 0 都需特殊处理, 写到这发现生成两个数的逻辑是一样的，所以提出去做util函数\n",
    "            nums1 = constructNumber(s[:i])\n",
    "\n",
    "            # 第二个数 s[i:]\n",
    "            nums2 = constructNumber(s[i:])\n",
    "\n",
    "            for n1 in nums1:\n",
    "                for n2 in nums2:\n",
    "                    res.append(f\"({n1}, {n2})\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "\n",
    "        # 可以扩展为n元坐标合法性的回溯\n",
    "\n",
    "        s = s[1:-1]\n",
    "        n = len(s)\n",
    "\n",
    "        def constructNumber(s):\n",
    "            i = len(s)\n",
    "\n",
    "            if s[0] == \"0\":\n",
    "                if i == 1:\n",
    "                    return [\"0\"]\n",
    "                elif i > 1 and s[i-1] == \"0\": #and int(s[:i]) == 0:\n",
    "                    return []\n",
    "                else:\n",
    "                    return [\"0.\" + s[1:i]]\n",
    "            elif s[i-1] == \"0\":\n",
    "                return [s[:i]]\n",
    "\n",
    "            #else:\n",
    "            nums = []\n",
    "            for j in range(1,i):\n",
    "                # [0,j-1] [j,i-1] interger/decimal   [0,0] [1,i-1] ... [0,i-1] [i,i-1] 只有整数\n",
    "                nums.append(s[:j] + \".\" +s[j:i])\n",
    "            nums.append(s[:i])\n",
    "            return nums\n",
    "\n",
    "        res = []\n",
    "        for i in range(1,n):\n",
    "            # [0,i-1] [i,n-1]\n",
    "            # s[:i]   s[i:]   for i = 1...n-1\n",
    "            \n",
    "            # 第一个数 如果start with 0/ end with 0 都需要特殊处理, 写完发现生成两个数的逻辑是一样的，提出去做util函数\n",
    "            nums1 = constructNumber(s[:i])\n",
    "\n",
    "            # 第二个数 s[i:]\n",
    "            nums2 = constructNumber(s[i:])\n",
    "\n",
    "            for n1 in nums1:\n",
    "                for n2 in nums2:\n",
    "                    res.append(f\"({n1}, {n2})\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        '''先枚举所有可能插入\",\"的x和y'''\n",
    "        i = 2\n",
    "        l = len(s)\n",
    "        ans = []\n",
    "        while i < l - 1:\n",
    "            xStr = s[1:i]\n",
    "            xlist = self.addpoint(xStr)\n",
    "            yStr = s[i:l - 1]\n",
    "            ylist = self.addpoint(yStr)\n",
    "            i += 1\n",
    "            for x in xlist:\n",
    "                for y in ylist:\n",
    "                    ans.append(\"({0}, {1})\".format(x, y))\n",
    "        \n",
    "        return ans\n",
    "\n",
    "    def addpoint(self, s: str) -> List[str]:\n",
    "        n = len(s)\n",
    "        i = 1\n",
    "        ans = []\n",
    "        while i < n:\n",
    "            left = s[0:i]\n",
    "            right = s[i:n]\n",
    "            i += 1\n",
    "            if left.startswith(\"0\") and len(left) > 1:\n",
    "                continue\n",
    "            if right.endswith(\"0\"):\n",
    "                continue\n",
    "            ans.append(left + \".\" + right)\n",
    "\n",
    "        if (len(s) > 1 and not s.startswith(\"0\")) or (len(s) == 1):\n",
    "            ans.append(s)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        res = []\n",
    "        def findSplit(s):\n",
    "            res = []\n",
    "            m = len(s)\n",
    "            if m == 0:\n",
    "                return res\n",
    "            if m == 1:\n",
    "                res.append(s)\n",
    "                return res\n",
    "            else:\n",
    "                if int(s[0]) > 0:\n",
    "                    res.append(s)\n",
    "                for i in range(0, m-1):\n",
    "                    if len(s[:i+1]) > 1 and s[0] == '0':\n",
    "                        continue\n",
    "                    if int(s[-1]) == 0:\n",
    "                        continue\n",
    "                    res.append(s[:i+1]+'.'+s[i+1:])\n",
    "            return res\n",
    "        n = len(s)\n",
    "        s = s[1:n-1]\n",
    "        \n",
    "        for i in range(n):\n",
    "            s1 = s[:i+1]\n",
    "            s2 = s[i+1:]\n",
    "            lst1 = findSplit(s1)\n",
    "            lst2 = findSplit(s2)\n",
    "            for a in lst1:\n",
    "                for b in lst2:\n",
    "                    res.append('('+a+', '+b+')')\n",
    "        \n",
    "        return res\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        def get_pos(s: str) -> List[str]:\n",
    "            pos = []\n",
    "            if s[0] != '0' or s == '0':\n",
    "                pos.append(s)\n",
    "            for p in range(1, len(s)):\n",
    "                if p != 1 and s[0] == '0' or s[-1] == '0':\n",
    "                    continue\n",
    "                pos.append(s[:p] + '.' + s[p:])\n",
    "            return pos\n",
    "\n",
    "        n = len(s) - 2\n",
    "        res = []\n",
    "        s = s[1: len(s) - 1]\n",
    "        for l in range(1, n):\n",
    "            lt = get_pos(s[:l])\n",
    "            if len(lt) == 0:\n",
    "                continue\n",
    "            rt = get_pos(s[l:])\n",
    "            if len(rt) == 0:\n",
    "                continue\n",
    "            for i, j in product(lt, rt):\n",
    "                res.append('(' + i + ', ' + j + ')')\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "\n",
    "        # 可以扩展为n元坐标合法性的回溯\n",
    "\n",
    "        s = s[1:-1]\n",
    "        n = len(s)\n",
    "\n",
    "        \n",
    "\n",
    "        def constructNumber(s):\n",
    "            i = len(s)\n",
    "            nums1 = []\n",
    "            if i == 1:\n",
    "                nums1.append(s[0])\n",
    "            elif s[0] == \"0\":\n",
    "                if i > 1 and s[i-1] == \"0\": #and int(s[:i]) == 0:\n",
    "                    return []\n",
    "                else:\n",
    "                    nums1.append(\"0.\" + s[1:i])\n",
    "            elif s[i-1] == \"0\":\n",
    "                nums1.append(s[:i])\n",
    "            else:\n",
    "                for j in range(1,i):\n",
    "                    # [0,j-1] [j,i-1] interger/decimal   [0,0] [1,i-1] ... [0,i-1] [i,i-1] 只有整数\n",
    "                    nums1.append(s[:j] + \".\" +s[j:i])\n",
    "                nums1.append(s[:i])\n",
    "            # print(nums1)\n",
    "            return nums1\n",
    "\n",
    "        res = []\n",
    "        for i in range(1,n):\n",
    "            # [0,i-1] [i,n-1]\n",
    "            # s[:i]   s[i:]   for i = 1...n-1\n",
    "            \n",
    "            #第一个数 如果start with 0/ end with 0 都需要特殊处理\n",
    "            nums1 = constructNumber(s[:i])\n",
    "\n",
    "            # 第二个数 s[i:]\n",
    "            nums2 = constructNumber(s[i:])\n",
    "\n",
    "            for n1 in nums1:\n",
    "                for n2 in nums2:\n",
    "                    res.append(f\"({n1}, {n2})\")\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def ambiguousCoordinates(self, s: str) -> List[str]:\n",
    "        # 符合规则数的集合\n",
    "        def findSplit(s:str)->List[str]:\n",
    "            lis=[]\n",
    "            # 判断整数是否符合规则\n",
    "            if len(s)==1 or s[0]!='0':\n",
    "                lis.append(s)\n",
    "            # 枚举小数点\n",
    "            for i in range(1,len(s)):\n",
    "                s1,s2=s[:i],s[i:]\n",
    "                # 判断小数是否符合规则\n",
    "                if (i==1 or s[0]!='0') and s2[-1]!='0':\n",
    "                    lis.append(s1+'.'+s2)\n",
    "            return lis\n",
    "        \n",
    "        n,ans=len(s),[]\n",
    "        # 去掉括号\n",
    "        s=s[1:n-1]\n",
    "        # 枚举逗号的位置\n",
    "        for i in range(1,n-2):\n",
    "            # 找到横纵坐标符合规则的数的集合\n",
    "            part1,part2=findSplit(s[:i]),findSplit(s[i:])\n",
    "            # 整合横纵坐标\n",
    "            for a in part1:\n",
    "                for b in part2:\n",
    "                    ans.append('('+a+', '+b+')')\n",
    "        return ans\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
